The long-term average statistics of flows in a network allows network administrators to plan future network upgrades. Such information can also lead to the identification of vagaries such as denial of service (DoS) attacks, switching loops, etc. in the network. The break-up of traffic based on the type of traffic is interesting to facilitate optimizations (such as strategic web-server caching) in the network. This makes the estimation of average flow throughput in a network useful.
Because a packet passes through multiple forwarding routers before reaching the destination, there is a need to prevent heavy-hitter flows (also referred to as “elephant flows”) from hogging forwarding path bandwidth and thus starving other flows that pass through the path. Heavy hitter flows refers to a flow whose bandwidth, either instantaneous or average, is significantly larger in proportion to other flows in a system. Congestion avoidance in the Internet is implemented in the form of TCP congestion control protocols, e.g., Reno/Tahoe/SACK at the end hosts. Assuming that the forwarding routers allocate buffers fairly among flows that pass through them, the steady state transmission control protocol (TCP) window size at the sender is equal to the fair buffer share at the bottleneck router. Typically routers augment the congestion collapse by using preferentially dropping schemes, e.g., random early detection (RED) and Blue, in order to pro-actively enforce fairness among flows that pass through them.
RED is a probabilistic mechanism that randomly marks packets based on queue size estimates. RED provides router-based queue management for TCP flows and because RED uses queue occupancy as the sole metric of congestion, there is always a finite probability that the wrong packet may be penalized, i.e., dropped.
BLUE is a class of queue management algorithms which use scalable fast binning techniques to probabilistically mark packets based on link-utilization and error-rates. Stochastic Fair BLUE uses an approximate scheme for binning packets in queues and then probabilistically drops packets based on queue sizes.
Prior approaches may problematically penalize a packet, i.e., drop the packet, for the flooding caused by another rogue flow.